/**
 * **inverse modulo 定义 ：**
 *
 * 模乘逆元定义：满足 ab≡1（mod m)，称b为a模乘逆元。以下是有关概念以及四种方法及程序。
 *
 * **例子：**
 *
 * ax = 1 (mod b), x即a的模逆。
 *
 * by = 1 (mod a)，y即b的模逆。
 *
 * **下面是代码**
 * @author Jarvan
 * @version 1.0
 * @create 2020/10/30 20:40
 */
public class T3 {
    void ext_gcd(int a, int b, int d, int x, int y) {
        if (b!=0) {
            d = a;
            x = 1;
            y = 0;
        } else {
            ext_gcd(b, a % b, d, y, x);
            y -= x * (a / b);
        }
    }

    int mod_inverse(int a, int m) {
        int x = 0, y = 0, d = 0;
        ext_gcd(a, m, d, x, y);
        return (m + x % m) % m;
    }

    public static void main(String[] args) {
        int i = new T3().mod_inverse(101, 4620);
        System.out.println(i);
    }

}
